package com.LeeCode;

/**
 * 零钱兑换
 */

public class Code322 {
    public static void main(String[] args) {
        int[] coins = {2};
        int amount = 3;
        int res = new Code322().coinChange(coins, amount);
        System.out.println(res);
    }

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];

        for (int i = 1; i <= amount; i++) {
            int tmp = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) { // 要能兑换才进行判断
                    tmp = Math.min(tmp, dp[i - coin] + 1);
                }
            }
            dp[i] = tmp;
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}
